//
//  Problem264.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/11.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 264. 丑数 II 【动态规划】【质数】
 编写一个程序，找出第 n 个丑数。
 丑数就是质因数只包含 2, 3, 5 的正整数。

 示例:
     输入: n = 10
     输出: 12
     解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
 说明:
    1 是丑数。
    n 不超过1690。
 */
@objcMembers class Problem264: NSObject {
    func solution() {
        print(nthUglyNumber(16))
//        print(nthUglyNumber(1010))
    }
    
    /*
     动态规划
     1 1 1
     [1 * 2] [1 * 3] [1 * 5] => 最小值是第一个：2，那么下一次 1 -> 下一个丑数(2)
     [2 * 2] [1 * 3] [1 * 5] => 最小值是第二个：3，那么下一次 1 -> 下一个丑数(2)
     [2 * 2] [2 * 3] [1 * 5] => 最小值是第一个：4，那么下一次 2 -> 下一个丑数(3)
     [3 * 2] [2 * 3] [1 * 5] => 5
     [3 * 2] [2 * 3] [2 * 5] => 6
     [4 * 2] [3 * 3] [2 * 5] => 8
     [5 * 2] [3 * 3] [2 * 5] => 9
     [5 * 2] [4 * 3] [2 * 5] => 10
     不是简单的 +1 而是：也是按照 2 3 4 5 6 8 9的顺序，必须是丑数
     */
    func nthUglyNumber(_ n: Int) -> Int {
        if n == 1 {
            return 1
        }
        
        var dp = Array(repeating: 0, count: n)
        var listValue = [1, 1, 1]
        var lastValue = [1, 1, 1]       // 记录每次的步数
        for i in 1..<n {
            dp[i] = min(listValue[0] * 2, listValue[1] * 3, listValue[2] * 5)
            if dp[i] == listValue[0] * 2 {
                listValue[0] = dp[lastValue[0]]
                lastValue[0] += 1
            }
            if dp[i] == listValue[1] * 3 {
                listValue[1] = dp[lastValue[1]]
                lastValue[1] += 1
            }
            if dp[i] == listValue[2] * 5 {
                listValue[2] = dp[lastValue[2]]
                lastValue[2] += 1
            }
        }
        
        return dp.last!
    }
}
